package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         373,
		Discription: "最长摆动子序列",
		Level:       2,
		Labels: map[string]int{
			"动态规划": 1,
			"有限状态机": 1,
			"贪心": 1,
		},
	})
}

func WiggleMaxLength(nums []int) int {
	n := len(nums)
	up := make([]int, n)
	down := make([]int, n)
	//up[i]表示nums[:i+1]中最长的最后一段是上升的子序列
	up[0] = 1
	//down[i]表示nums[:i+1]中最长的最后一段是下降的子序列
	down[0] = 1
	for i := 1; i < n; i++ {
		if nums[i] == nums[i-1] {
			//最长子序列里不会同时包含i和i-1，所以up[i] up[i-1]一样
			up[i] = up[i-1]
			down[i] = down[i-1]
			continue
		}

		if nums[i] < nums[i-1] {
			//i-1到i是下降的，不可能作为上升子序列的最后一段
			up[i] = up[i-1]
			//如果up[i-1]的最长子序列是以一个比当前nums[i]要小的数结尾的（这样和nums[i]组合最后一段不是下降），可以把这最后一个数换成nums[i-1]（这样最后一段变成下降了），且不影响up[i-1]的值
			down[i] = max(down[i-1], up[i-1]+1)
		} else {
			up[i] = max(up[i-1], down[i-1]+1)
			down[i] = down[i-1]
		}
	}

	return max(up[n-1], down[n-1])
}